/**
 * 升序
 */
public class InsertSort {

    public static int[] insertSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return null;
        for(int i=1; i<arr.length; i++) { //假设第一个数位置是正确的；
            int j = i;
            int target = arr[i]; //待插入的
            //后移
            while(j > 0 && target < arr[j-1]) {
                arr[j] = arr[j-1];
                j --;
            } //插入
            arr[j] = target;
        }
        return arr;
    }

    public static void main(String[] args) {
        for (int x :
                insertSort(new int[]{8,6,5,4,8,65,54,786,47,8,6,554,5,6,5})
        ) {
            System.out.println(x);
        }
    }
}
/**
 *
 */